package com.dhu.graph.digraph;

import com.dhu.graph.basic.GraphImpls.DiGraph;
import com.dhu.graph.basic.GraphImpls.EdgeWeightedDiGraph;
import com.dhu.graph.basic.edge.DirectedEdge;

import java.util.Stack;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-06
 * @ Description：无环五无向图的拓扑排序(逆后序）
 * @ Modified By：
 * @ Version:
 */
public class TopoLogical {
    private boolean[] marked;

    private Stack<Integer> order;   // 顶点的额拓扑排序

    public TopoLogical(DiGraph G){
        DirectedCycle cycle = new DirectedCycle(G);
        if(!cycle.hasCycle()){
            DepthFirstSort depthFirstSort = new DepthFirstSort(G);
            order = depthFirstSort.reversePost();
        }
    }
    public TopoLogical(EdgeWeightedDiGraph G){
        this.order = new Stack<Integer>();
        this.marked = new boolean[G.V()];
        for (int i = 0; i < G.V(); i++) {
            if (!marked[i]) dsf(G, i);
        }
    }
    private void dsf(EdgeWeightedDiGraph G, int s){
        marked[s] = true;
        for (DirectedEdge e : G.adj(s)) {
            if (!marked[e.to()])
                dsf(G, e.to());
        }
        order.push(s);
    }

    public Stack<Integer> order(){
        return this.order;
    }
    // 该图是无环图吗
    public boolean isDAG(){
        return this.order == null;
    }
}
